前缀树结构和Java代码实现

#前缀树结构和Java代码实现| 来源: 网络整理| 查看: 265

以前在项目中使用过前缀对敏感词进行过滤，现在就详细说一下他的结构和如何实现吧。

结构的3个基本性质： 1. 根节点不包含字符，除根节点外每一个节点都只包含一个字符。 2. 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。 3. 每个节点的所有子节点包含的字符都不相同。

前缀的好处：前缀树可以最大限度地减少无谓的字符串比较，查询效率非常高。前缀树的核心思想是利用空间换时间，利用字符串的公共前缀来降低查询时间的开销达到提高效率的目的。

Java代码实现

/** * author: zzw5005 * date: 2019/1/10 10:24 */ public class Trie { private class Node { Node[] childs = new Node[26]; boolean isLeaf; } private Node root = new Node(); public Trie() { } public void insert(String word) { insert(word, root); } private void insert(String word, Node node) { if (node == null) return; if (word.length() == 0) { node.isLeaf = true; return; } int index = indexForChar(word.charAt(0)); if (no

【本文地址】

公司简介

联系我们